/**
 * 给定有序数组A和t，找到等于t的子段
 * x x x t t t y y y 
 * 0 0 0 1 1 1 1 1 1
 * 令函数为 t <= A[i] ? 1 : 0，则找出第一个为1的位置
 * 
 * x x x t t t y y y
 * 0 0 0 0 0 0 1 1 1
 * 再令函数为 t < A[i] ? 1 : 0，找出最后一个为0的位置
 * 
 * 即可。注意区间不存在以及解不存在的情况
 */

int bsLast0(int start, int end, function<int(int)> f){
	assert(left <= right);
    int left = start, right = end, mid;
	do{
        mid = (left + right) >> 1;
		auto tmp = f(mid);
		assert(0 == tmp or 1 == tmp);
		if(tmp == 1) right = mid - 1;
		else left = mid + 1; 
	}while(left <= right);
	return right;
}

int bsFirst1(int start, int end, function<int(int)> f){
	assert(left <= right);
    int left = start, right = end, mid;
	do{
        mid = (left + right) >> 1;
		auto tmp = f(mid);
		assert(0 == tmp or 1 == tmp);
		if(tmp == 1) right = mid - 1;
		else left = mid + 1; 
	}while(left <= right);
	return left;
}

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int n = nums.size();
		if(0 == n) return {-1, -1};
		int u = bsFirst1(0, n - 1, [&nums, target](int pos)->int{return target <= nums[pos] ? 1 : 0;});
		int v = bsLast0(0, n - 1, [&nums, target](int pos)->int{return target < nums[pos] ? 1 : 0;});
		if(u > v) return {-1, -1};
		return {u, v};
    }
};